package com.lfs.dp;

/*
    零钱兑换2
    完全背包
    与494完全相似，494是01背包，本题是完全背包
 */
public class CoinsChange518 {
    /*
        这里求组合数，不讲究排列 [1,5][5,1] 是一个元素
        先遍历物品 再 背包容量 : 求 组合数
        先遍历背包 再 物品数量 : 求 排列数

        本题一定要先物品再背包
          1.状态定义:dp[j]装满 j 最多有dp[j]种方法
          2.递推公式:
            dp[j] += dp[j-coins[i]]
          3.初始化: dp[0] = 1 非零dp = 0(防止影响其他值的累加操作)
     */
    /*
        关于组合和排列的问题还是有些不解。以下仅为自己的理解：先遍历物品后遍历背包是这样，
        比如，外层循环固定coins【1】，在内层循环遍历背包时，随着背包不断增加，coins【1】可以重复被添加进来，
        而由于外层循环固定了，因此coins【2】只能在下一次外层循环添加进不同大小的背包中，
        这么看的话，coins【i+1】只能在coins【i】之后了；如果先遍历背包后遍历物品，那么外层循环先固定背包大小j，
        然后在大小为j的背包中循环遍历添加物品，然后在下次外层循环背包大小变为j+1，此时仍要执行内层循环遍历添加物品，
        也就会出现在上一轮外层循环中添加coins【2】的基础上还能再添加coins【1】的情况，那么就有了coins【1】在coins【2】之后的情况了
     */

    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];

        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {//容量大于等于货币时
                    dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}
